Finite State Machine

(FSM or "Finite State Automaton",

"transducer") An {abstract machine} consisting of a set of

{states} (including the initial state), a set of input events,

a set of output events and a state transition function. The

function takes the current state and an input event and

returns the new set of output events and the next state. Some

states may be designated as "terminal states". The state

machine can also be viewed as a function which maps an ordered

sequence of input events into a corresponding sequence of

(sets of) output events.

A {deterministic} FSM is one where the next state is uniquely

determinied by a single input event. A {nondeterministic} FSM

(NFA) may have several next states for a given input event,

which one is actually chosen may either be random or,

according to a different definition, it may depend on an

arbitrary number of subsequent input events. In the latter

case, until these subsequent events occur it is not possible

to determine which state the machine is in.

It is possible to automatically translate a nondeterministic

FSM into a deterministic one which will produce the same

output given the same input. [Is this true?]

FSMs are used in {computability theory} and in some practical

applications such as {regular expressions} and digital logic

design.

See also {state transition diagram}, {Turing Machine}.

[J.H. Conway, "regular algebra and finite machines", 1971, Eds

Chapman & Hall].

[S.C. Kleene, "Representation of events in nerve nets and

finite automata", 1956, Automata Studies. Princeton].

[Hopcroft & Ullman, 1979, "Introduction to automata theory,

languages and computations", Addison-Wesley].

(2000-08-05)